Exponentiation is a fundamental operation in many cryptographic applications, such as multi-party public key cryptography protocols. In such applications, there is often a need for the parties involved to prove to each other that the correct computation was performed, e.g., to prove that the intended exponentiation in relation to some public key was performed. However, in many multi-party protocols, whose robustness may depend on these types of proofs, it is not known beforehand whether the relation holds or not. Therefore, if the proof for proving a correct exponentiation requires that the computation indeed was correctly performed, then such a protocol may leak important information when given invalid inputs. This in turn may endanger protocol properties, such as privacy, as it potentially allows attacks on the protocol.
An example of a protocol which may leak information when given invalid inputs is based on the techniques described in D. Chaum and H. Van Antwerpen, “Undeniable Signatures,” Advances in Cryptology-Proceedings of Crypto '89, pp. 212–216, which attempt to determine whether a given quadruple (g, y, m, s) satisfies the relation loggy=logms in the context of verifying the validity of undeniable signatures. These techniques have been extended in D. Chaum, “Zero-Knowledge Undeniable Signatures,” Eurocrypt, '90, pp. 458–464, to a signature validity verification protocol which is zero-knowledge for valid inputs. However, it is assumed in this protocol that the prover knows whether the signature is valid or not. This is a serious deficiency of the protocol, since by running the zero-knowledge proof for an invalid input, the prover in fact leaks information regarding the corresponding valid signature. As a result, for invalid inputs, a standard distinguishing protocol, e.g., similar to a protocol suitable for proving graph non-isomorphism, must be used. T. P. Pedersen, “Distributed Provers with Applications to Undeniable Signatures,” Advances in Cryptology-Proceedings of EuroCrypt '91, pp. 221–242, discloses how to distribute the zero-knowledge method for proving validity of undeniable signatures, but still under the above-noted problematic assumption that the prover already knows whether the input is a valid undeniable signature.
It is therefore desirable to design protocols that do not leak any information whether given valid or invalid inputs. Since the very aim of the protocol may be to determine whether the input is valid or not, the protocol should preferably comprise two sub-protocols, one for valid inputs and the other for invalid inputs, such that the behavior of a prover is identical for both sub-protocols. A protocol described in A. Fujioka et al., “Interactive Bi-Proof Systems and Undeniable Signature Techniques,” Eurocrypt '91, pp. 243–256 is symmetric in the sense that it contains two identical portions for the prover, one for proving validity of undeniable signatures, the other for proving invalidity. It is not clear, however, how to distribute the protocol.
Such a protocol is referred to as “oblivious,” since it does not require the protocol participants to know beforehand whether the input is of one type or another in order to correctly perform the computation. The term “oblivious” was coined by M. Jakobsson and M. Yung, “Proving Without Knowing: On Oblivious, Agnostic and Blindfolded Provers,” Crypto '96, pp. 186–200, in proposing a multi-party protocol for determining whether a given exponentiation was correctly performed. Their protocol allows the distribution of the prover in a setting in which the prover cannot learn whether the input is valid or not. However, this protocol generally requires computation and communication operations that are logarithmic in the length of the security parameter, e.g., requires O(k) rounds and exponentiations in order to reduce the failure probability to O(2−k), which may be a limiting consideration in certain applications.